Deadlocks can occur in computer systems that use locking for synchronization when cycles occur in the directed graphs of lock waits. Such deadlocks can halt processing, crash programs, or significantly reduce computing efficiency. As such, various different schemes have been developed to avoid deadlocks.
Some traditional schemes use global serializing operations around possible deadlock situations. Such schemes avoid a deadlock at the expense of severely limiting potential parallel processing. Additional schemes attempt to impose a convention of deadlock avoidance by defining a-priori lock hierarchies that always acquire locks in the same global order. Such locks are often acquired with mediating or global ordering locks at the expense of unnecessary lock acquisitions when no conflicts exist. Still other methods require observing all current lock operations in the system with graph operations to detect cycles (deadlocks) and resolve them with a set of heuristic techniques. For instance, some schemes use a centralized lock manager that must be able to examine all lock states in the system.
These prior schemes to avoid deadlocks pose problems in clustered file systems and other clustered software (e.g., database application software written to exploit the inherent parallelism of a clustered environment) that try to coordinate the actions of otherwise potentially conflicting operations across multiple cluster nodes.